Recursive insert with duplicate check. Trace inserting key 60.
def insert(node, key):
# Base case: if the subtree is empty,
# create and return a new node
if node is None:
return Node(key)
# Duplicate key: do nothing (no duplicates)
if key == node.key:
return node
# Recur down the tree
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
# Return the (possibly updated) node pointer
return node